// Copyright [2020] <unknown>
#include <bits/stdc++.h>
using namespace std;
// #define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#define dbg(x...) { cerr << "\033[32;1m" << #x << " -> "; err(x); }
void err() { cerr << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif

#define sz(x) ((int)x.size())

typedef long long LL;

int t, n;

struct P {
    vector<int> a;
    P () {}
    P (vector<int> a) {
        this->a = a;
    }
    P shift(int i, int l) const {
        int n = a.size();
        assert(i+l-1 < n);
        P b(a);
        // exit(0);
        vector<int> &v = b.a;
        for (int j=0; j<l; ++j) {
            v[j + i] = a[i + (j+1)%l];
        }
        return b;
    }
    string output() const {
        char s[1000];
        int cur = 0;
        for (int i=0; i<sz(a); ++i) {
            sprintf(s + cur, "%d ", a[i]);
            cur = strlen(s);
        }
        return string(s);
    }

    bool operator < (const P &other) const {
        int n = a.size();
        for (int i=0; i<n; ++i)
            if (a[i] != other.a[i])
                return a[i] < other.a[i];
        return false;
    }

    bool operator == (const P &other) const {
        for (int i=0; i<sz(a); ++i)
            if (a[i] != other.a[i])
                return false;
        return true;
    }
};

int f[10000000];

P dat[10000000];

int main(int argc, char const *argv[]) {
    // code

    int l = 8, n = 9;
    vector<int> a = {0, 1, 2, 3, 4, 5, 6, 7, 8};
    map<P, int> mp;
    int cnt = 0;
    // S.insert(a);
    mp[a] = ++cnt;
    while (1) {

        vector<pair<P, int>> newv;
        for (const auto &p : mp) {
            int nowid = p.second;
            for (int i=0; i+l-1<n; ++i) {
                P newp = p.first.shift(i, l);
                // dbg(newp.output());
                if (!mp.count(newp)) {
                    newv.push_back(make_pair(newp, nowid));
                }
            }
        }
        if (!newv.size())
            break;
        else {
            // sort(newv.begin(), newv.end());
            // newv.resize(unique(newv.begin(), newv.end()) - newv.begin());
            for (const auto &p : newv) {
                if (mp.count(p.first))
                    continue;
                f[++cnt] = p.second;
                mp[p.first] = cnt;
            }
        }
    }

    for (const auto &p : mp)
        dat[p.second] = p.first;
        // cout << p.first.output() << ' ' << p.second << endl;
    // dbg(S.size());
    dbg(cnt);
    P tar({0, 1, 2, 3, 4, 5, 7, 6, 8});
    int id = mp[tar];
    while (id != 1) {
        dbg(id, dat[id].output());
        id = f[id];

    }
    return 0;
}
